package 典型.回溯法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 有重复数字的全排列全排列 https://leetcode-cn.com/problems/permutations-ii/
public class LC47 {

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums==null||nums.length==0) return res;
        Arrays.sort(nums);
        // 增加一个数组参数，维护当前位置的数是否出现过重复值
        backTrack(res,new ArrayList<Integer>(),nums,new boolean[nums.length]);
        return res;
    }
    public static void backTrack(List<List<Integer>> res, List<Integer> list,int[] nums,boolean [] use){
        if(list.size()==nums.length){
            res.add(new ArrayList<>(list));
        }
        else{
            for(int i=0;i<nums.length;i++){
                //注意这种引入辅助数组对的去重方法
                if(use[i]||i!=0&&nums[i]==nums[i-1]&&use[i-1]) continue;
                use[i] = true;
                list.add(nums[i]);
                backTrack(res,list,nums,use);
                //为了回溯的时候能够恢复初始条件必须将use恢复
                use[i] = false;
                list.remove(list.size()-1);
            }
        }
    }
    public static void main(String[] args) {
        System.out.println(permuteUnique(new int[]{1, 2, 2 ,2, 4}));
    }

}
